class Solution(object):
    def containsNearbyAlmostDuplicate(self, nums, k, t):
        """
        :type nums: List[int]
        :type k: int
        :type t: int
        :rtype: bool
        """
        already_dict = {}
        for i in range(len(nums)):
            a = nums[i] // (t + 1)
            if a in already_dict:
                if abs(i - already_dict[a]) <= k:
                    return True
                else:
                    already_dict[a] = i
            else:
                already_dict[a] = i
            if a - 1 in already_dict:
                if abs(already_dict[a - 1] - i) <= k and abs(nums[already_dict[a - 1]] - nums[i]) <= t:
                    return True
            if a + 1 in already_dict:
                if abs(already_dict[a + 1] - i) <= k and abs(nums[already_dict[a + 1]] - nums[i]) <= t:
                    return True
        return False

data = Solution()
nums = [1, 2, 3, 1]
k = 3
t = 0
print(data.containsNearbyAlmostDuplicate(nums, k, t))
nums = [1,5,9,1,5,9]
k = 2
t = 3
print(data.containsNearbyAlmostDuplicate(nums, k, t))
nums = [1,2,3,1]
k = 3
t = 0
print(data.containsNearbyAlmostDuplicate(nums, k, t))
nums = [2147483647,-1,2147483647]
k = 1
t = 2147483647
print(data.containsNearbyAlmostDuplicate(nums, k, t))
nums = [3, 6, 0, 4]
k = 2
t = 2
print(data.containsNearbyAlmostDuplicate(nums, k, t))